"""
动态规划实在看不出来，但是回溯还是会写的。。。
提交超时了，优化了一下，发现超过递归深度了。。
"""
class Solution:
    def waysToChange(self, n: int) -> int:
        ans = 0
        d = [25, 10, 5, 1]
        def helper(n, start):
            nonlocal ans
            print(n, start)
            if n == 0 or start == 3:
                ans+=1
                return
            for i in range(start, len(d)):
                if n >= d[i]:
                    helper(n-d[i], i)
        helper(n, 0)
        return ans % 1000000007

# class Solution:
#     def waysToChange(self, n: int) -> int:
#         mod = 10**9 + 7
#         coins = [25, 10, 5, 1]

#         f = [1] + [0] * n
#         for coin in coins:
#             for i in range(coin, n + 1):
#                 f[i] += f[i - coin]
#                 print(f, i)
#         return f[n] % mod

if __name__ == "__main__":
    r = Solution().waysToChange(900750)
    print(r)